package com.interview.javabase.algorithm.动态规划;

import java.util.Arrays;
import java.util.Comparator;

/**
 * @author www.byteblogs.com
 * @date 2021-10-06
 * @since 2.0
 */
public class 二维数据递增子序列信封嵌套问题 {

    public static void main(String[] args) {

        int[][] arr = new int[4][2];
        arr[0][0] = 5;
        arr[0][1] = 4;
        arr[1][0] = 6;
        arr[1][1] = 4;
        arr[2][0] = 6;
        arr[2][1] = 7;
        arr[3][0] = 2;
        arr[3][1] = 3;

        System.out.println(lengthOfLIS(arr));
    }

    static int lengthOfLIS(int[][] nums) {
        Arrays.sort(nums, new Comparator<int[]>() {
            @Override
            public int compare(int[] a, int[] b) {
                return a[0] == b[0] ? b[1] - a[1] : a[0] - b[0];
            }
        });

        int[] height = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            height[i] = nums[i][0];
        }

        return lengthOfLIS(height);
    }

    static int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length];

        Arrays.fill(dp, 1);

        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }

        int result = 0;
        for (int i = 0; i < dp.length; i++) {
            result = Math.max(result, dp[i]);
        }

        return result;
    }
}
